package own.stu.jobgib.playown.alg.solution.binarySearch;

public class LongSeq {

    public static void main(String[] args) {
        LongSeq s = new LongSeq();
        System.out.println(s.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(s.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        System.out.println(s.lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7}));
    }

    /**
     * 300. 最长递增子序列
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * <p>
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     */
    public int lengthOfLIS(int[] nums) {
        /*
        总体的思想是贪心：在长度相同的情况下，最后的数字小的话，那么其继续增长的趋势更大
        思路：定义 数组 d[n] 默认 d[0] = nums[0],
        nums[i]
        1： 大于最后一个数字d[n - 1] 时，表示可以继续增长，将 d[n] len + 1, d[n - 1] = nums[i]
        2: 小于最后一个数字时，二分查找到最后一个小于nums[i]的元素d[i]，将d[i + 1] 替换为nums[i]
         */
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] d = new int[n];
        d[0] = nums[0];
        int idx = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > d[idx]) {
                idx++;
                d[idx] = nums[i];
            } else {
                int l = 0, r = idx, pos = -1;
                while (l + 1 < r) {
                    int m = l + ((r - l) >> 1);
                    if (d[m] >= nums[i]) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                if (d[r] < nums[i])
                    pos = r;
                else if (d[l] < nums[i])
                    pos = l;
                d[pos + 1] = nums[i];
            }
        }
        /*for (int i : d) {
            System.out.print(i + ", ");
        }
        System.out.println();*/
        return idx + 1;
    }
}
